package Tree;

import java.util.ArrayList;
import java.util.List;

public class 路径总和2 {
    private List<List<Integer>> result = new ArrayList<>();
    private List<Integer> path = new ArrayList<>();

    public List<List<Integer>> pathSum(TreeNode root, int targetSum) {
        getPathSum(root, targetSum);
        return result;
    }

    private void getPathSum(TreeNode root, int sum) {
        if (root == null) return;
        path.add(root.val);
        if (root.left == null && root.right == null && sum == root.val) result.add(new ArrayList<>(path));
        getPathSum(root.left, sum - root.val);
        getPathSum(root.right, sum - root.val);
        path.removeLast(); // 回溯

        // 易于理解
        /*if (root.left != null) {
            getPathSum(root.left, sum - root.val);
            path.removeLast(); // 回溯
        }
        if (root.right != null) {
            getPathSum(root.right, sum - root.val);
            path.removeLast(); // 回溯
        }*/
    }
}
